package Hard;

// 879.盈利计划
// 想明白了不能用暴力做，于是看答案
// 答案用动态规划做，因为本质是一个背包问题
// n个人相当于背包容量，minProfit相当于要求我背包里最少装的价值，group代表每个物品的重量，profit代表每个物品的价值
// 对于第i个物品，dp[j][k]表示截止到第i个物品时，用j大小的容量，获取k的价值，有dp[j][k]条策略
// 初始化dp[M][0] = 1; M=1,2,3,...n 解释：对于M大小的容量，初始情况下想要获取0的价值，只有一种方案，就是什么都不放。（现在还没有遍历过所有物品，有的物品价值是为0的）
// 设w为第i个物品的重量，v为第i个物品的价值
// dp[j][k] = dp[j-w][k-v] + dp[j][k] ,如果k-v<0,则k-v视为0
// 解释：要想j的重量至少装k价值的方法，就等于j-w的重量至少装k-v的价值的方法的数量，但是要遍历所有物品，所以每次还要加上已有方法的数量
// 本质：看看当前物品能不能放到背包里面
public class Solution879 {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        final int M = 1_000_000_007;
        int pojo = group.length; // 物品个数
        int[][] dp = new int[n+1][minProfit+1];
        for (int i = 0; i < n+1; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < pojo; i++) {
            int w = group[i];
            int v = profit[i];
            // 这里循环要倒着写，如果正着写，会让dp[M][0]=1的值，多加到后面去
            // 为什么可以倒着写呢？ 因为每次dp更新的时候，依赖的是过去的自己的两个状态，和新物品是否进来无关
            for(int j = n; j >=w ; j--){
                for(int k = minProfit ; k >=0 ; k--){
                    dp[j][k]+=dp[j-w][Math.max(0,k-v)];
                    dp[j][k]%=M;
                }
            }
        }
        return dp[n][minProfit];
    }

    public static void main(String[] args) {
        Solution879 s = new Solution879();
        s.profitableSchemes(5,3,new int[]{2,2},new int[]{2,3});
    }
}
